//剑指22：链表的倒数第K个结点
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //顺序查找 （时间复杂度为O(n),空间复杂度为O(1)）
        if(head==null) return null;
        ListNode cur = head;
        int len = 0;
        while(cur!=null){
            cur = cur.next;
            len++;
        }
        cur = head;
        while(len>k){
            cur = cur.next;
            len--;
        }
        return cur;
    }
}

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        //快慢指针法
        ListNode slow = head;
        ListNode fast = head;
        while(k-1>0){
            fast = fast.next;
            k--;
        }
        while(fast.next!=null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}